<!DOCTYPE html>
<html lang=zh>
<head>
  <meta charset="utf-8">
  
  <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, minimum-scale=1, user-scalable=no, minimal-ui">
  <meta name="renderer" content="webkit">
  <meta http-equiv="Cache-Control" content="no-transform" />
  <meta http-equiv="Cache-Control" content="no-siteapp" />
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="apple-mobile-web-app-status-bar-style" content="black">
  <meta name="format-detection" content="telephone=no,email=no,adress=no">
  <!-- Color theme for statusbar -->
  <meta name="theme-color" content="#000000" />
  <!-- 强制页面在当前窗口以独立页面显示,防止别人在框架里调用页面 -->
  <meta http-equiv="window-target" content="_top" />
  
  
  <title>redis数据类型 | Skyung-Blog</title>
  <meta name="description" content="redis数据类型和实现原理">
<meta property="og:type" content="article">
<meta property="og:title" content="redis数据类型">
<meta property="og:url" content="https://skyung.gitee.io/Skyung/2022/03/01/redis%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86/index.html">
<meta property="og:site_name" content="Skyung-Blog">
<meta property="og:description" content="redis数据类型和实现原理">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://gitee.com/lifuh/picgo/raw/master/img/image-20220301171312134.png">
<meta property="og:image" content="https://gitee.com/lifuh/picgo/raw/master/img/image-20220301171325991.png">
<meta property="og:image" content="https://gitee.com/lifuh/picgo/raw/master/img/image-20220301171343457.png">
<meta property="og:image" content="https://gitee.com/lifuh/picgo/raw/master/img/image-20220301171410132.png">
<meta property="article:published_time" content="2022-02-28T16:00:00.000Z">
<meta property="article:modified_time" content="2022-02-28T16:00:00.000Z">
<meta property="article:author" content="Skyung">
<meta property="article:tag" content="redis">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/lifuh/picgo/raw/master/img/image-20220301171312134.png">
  <!-- Canonical links -->
  <link rel="canonical" href="https://skyung.gitee.io/Skyung/2022/03/01/redis%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86/index.html">
  
    <link rel="alternate" href="/atom.xml" title="Skyung-Blog" type="application/atom+xml">
  
  
    <link rel="icon" href="images/favicon.png" type="image/x-icon">
  
  
<link rel="stylesheet" href="/Skyung/css/style.css">

  
  
  
  
<meta name="generator" content="Hexo 5.4.1"></head>


<body class="main-center" itemscope itemtype="http://schema.org/WebPage">
  <header class="header" itemscope itemtype="http://schema.org/WPHeader">
  <div class="slimContent">
    <div class="navbar-header">
      
      
      <div class="profile-block text-center">
        <a id="avatar" href="https://github.com/cofess" target="_blank">
          <img class="img-circle img-rotate" src="/Skyung/images/avatar.jpg" width="200" height="200">
        </a>
        <h2 id="name" class="hidden-xs hidden-sm">Skyung</h2>
        <h3 id="title" class="hidden-xs hidden-sm hidden-md">Web Developer</h3>
        <small id="location" class="text-muted hidden-xs hidden-sm"><i class="icon icon-map-marker"></i> Wuhan, China</small>
      </div>
      
      <div class="search" id="search-form-wrap">

    <form class="search-form sidebar-form">
        <div class="input-group">
            <input type="text" class="search-form-input form-control" placeholder="搜索" />
            <span class="input-group-btn">
                <button type="submit" class="search-form-submit btn btn-flat" onclick="return false;"><i class="icon icon-search"></i></button>
            </span>
        </div>
    </form>
    <div class="ins-search">
  <div class="ins-search-mask"></div>
  <div class="ins-search-container">
    <div class="ins-input-wrapper">
      <input type="text" class="ins-search-input" placeholder="想要查找什么..." x-webkit-speech />
      <button type="button" class="close ins-close ins-selectable" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
    </div>
    <div class="ins-section-wrapper">
      <div class="ins-section-container"></div>
    </div>
  </div>
</div>


</div>
      <button class="navbar-toggle collapsed" type="button" data-toggle="collapse" data-target="#main-navbar" aria-controls="main-navbar" aria-expanded="false">
        <span class="sr-only">Toggle navigation</span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
      </button>
    </div>
    <nav id="main-navbar" class="collapse navbar-collapse" itemscope itemtype="http://schema.org/SiteNavigationElement" role="navigation">
      <ul class="nav navbar-nav main-nav ">
        
        
        <li class="menu-item menu-item-home">
          <a href="/Skyung/.">
            
            <i class="icon icon-home-fill"></i>
            
            <span class="menu-title">首页</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-archives">
          <a href="/Skyung/archives">
            
            <i class="icon icon-archives-fill"></i>
            
            <span class="menu-title">归档</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-categories">
          <a href="/Skyung/categories">
            
            <i class="icon icon-folder"></i>
            
            <span class="menu-title">分类</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-tags">
          <a href="/Skyung/tags">
            
            <i class="icon icon-tags"></i>
            
            <span class="menu-title">标签</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-repository">
          <a href="/Skyung/repository">
            
            <i class="icon icon-project"></i>
            
            <span class="menu-title">项目</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-books">
          <a href="/Skyung/books">
            
            <i class="icon icon-book-fill"></i>
            
            <span class="menu-title">书单</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-links">
          <a href="/Skyung/links">
            
            <i class="icon icon-friendship"></i>
            
            <span class="menu-title">友链</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-about">
          <a href="/Skyung/about">
            
            <i class="icon icon-cup-fill"></i>
            
            <span class="menu-title">关于</span>
          </a>
        </li>
        
      </ul>
      
	
    <ul class="social-links">
    	
        <li><a href="/Skyung/null" target="_blank" title="Github" data-toggle=tooltip data-placement=top><i class="icon icon-github"></i></a></li>
        
        <li><a href="/Skyung/null" target="_blank" title="Weibo" data-toggle=tooltip data-placement=top><i class="icon icon-weibo"></i></a></li>
        
        <li><a href="/Skyung/null" target="_blank" title="Twitter" data-toggle=tooltip data-placement=top><i class="icon icon-twitter"></i></a></li>
        
        <li><a href="/Skyung/null" target="_blank" title="Behance" data-toggle=tooltip data-placement=top><i class="icon icon-behance"></i></a></li>
        
        <li><a href="/Skyung/atom.xml" target="_blank" title="Rss" data-toggle=tooltip data-placement=top><i class="icon icon-rss"></i></a></li>
        
    </ul>

    </nav>
  </div>
</header>

  
    <aside class="sidebar" itemscope itemtype="http://schema.org/WPSideBar">
  <div class="slimContent">
    
      <div class="widget">
    <h3 class="widget-title">公告</h3>
    <div class="widget-body">
        <div id="board">
            <div class="content">
                <p>欢迎交流与分享经验!</p>
            </div>
        </div>
    </div>
</div>

    
      
  <div class="widget">
    <h3 class="widget-title">分类</h3>
    <div class="widget-body">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/Skyung/categories/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">学习笔记</a><span class="category-list-count">20</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">标签</h3>
    <div class="widget-body">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/Skyung/tags/java/" rel="tag">java</a><span class="tag-list-count">19</span></li><li class="tag-list-item"><a class="tag-list-link" href="/Skyung/tags/jvm/" rel="tag">jvm</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/Skyung/tags/linux/" rel="tag">linux</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/Skyung/tags/redis/" rel="tag">redis</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/Skyung/tags/%E5%A4%9A%E7%BA%BF%E7%A8%8B/" rel="tag">多线程</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/Skyung/tags/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/" rel="tag">并发编程</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/Skyung/tags/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" rel="tag">设计模式</a><span class="tag-list-count">4</span></li><li class="tag-list-item"><a class="tag-list-link" href="/Skyung/tags/%E9%9B%B6%E6%95%A3%E7%82%B9/" rel="tag">零散点</a><span class="tag-list-count">1</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">标签云</h3>
    <div class="widget-body tagcloud">
      <a href="/Skyung/tags/java/" style="font-size: 14px;">java</a> <a href="/Skyung/tags/jvm/" style="font-size: 13px;">jvm</a> <a href="/Skyung/tags/linux/" style="font-size: 13px;">linux</a> <a href="/Skyung/tags/redis/" style="font-size: 13px;">redis</a> <a href="/Skyung/tags/%E5%A4%9A%E7%BA%BF%E7%A8%8B/" style="font-size: 13px;">多线程</a> <a href="/Skyung/tags/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/" style="font-size: 13.33px;">并发编程</a> <a href="/Skyung/tags/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" style="font-size: 13.67px;">设计模式</a> <a href="/Skyung/tags/%E9%9B%B6%E6%95%A3%E7%82%B9/" style="font-size: 13px;">零散点</a>
    </div>
  </div>

    
      
  <div class="widget">
    <h3 class="widget-title">归档</h3>
    <div class="widget-body">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/Skyung/archives/2022/05/">五月 2022</a><span class="archive-list-count">5</span></li><li class="archive-list-item"><a class="archive-list-link" href="/Skyung/archives/2022/04/">四月 2022</a><span class="archive-list-count">7</span></li><li class="archive-list-item"><a class="archive-list-link" href="/Skyung/archives/2022/03/">三月 2022</a><span class="archive-list-count">9</span></li><li class="archive-list-item"><a class="archive-list-link" href="/Skyung/archives/2022/02/">二月 2022</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/Skyung/archives/2021/09/">九月 2021</a><span class="archive-list-count">1</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">最新文章</h3>
    <div class="widget-body">
      <ul class="recent-post-list list-unstyled no-thumbnail">
        
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                <a class="category-link" href="/Skyung/categories/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">学习笔记</a>
              </p>
              <p class="item-title">
                <a href="/Skyung/2022/05/08/Spring/" class="title">spring</a>
              </p>
              <p class="item-date">
                <time datetime="2022-05-07T16:00:00.000Z" itemprop="datePublished">2022-05-08</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                <a class="category-link" href="/Skyung/categories/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">学习笔记</a>
              </p>
              <p class="item-title">
                <a href="/Skyung/2022/05/08/netty-RPC/" class="title">Netty-RPC</a>
              </p>
              <p class="item-date">
                <time datetime="2022-05-07T16:00:00.000Z" itemprop="datePublished">2022-05-08</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                <a class="category-link" href="/Skyung/categories/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">学习笔记</a>
              </p>
              <p class="item-title">
                <a href="/Skyung/2022/05/07/%E5%B8%B8%E7%94%A8%E7%B1%BB%E5%BA%93%E5%92%8CAPI/" class="title">常见类库</a>
              </p>
              <p class="item-date">
                <time datetime="2022-05-06T16:00:00.000Z" itemprop="datePublished">2022-05-07</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                <a class="category-link" href="/Skyung/categories/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">学习笔记</a>
              </p>
              <p class="item-title">
                <a href="/Skyung/2022/05/07/%E5%8D%95%E5%85%83%E6%B5%8B%E8%AF%95/" class="title">单元测试</a>
              </p>
              <p class="item-date">
                <time datetime="2022-05-06T16:00:00.000Z" itemprop="datePublished">2022-05-07</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                <a class="category-link" href="/Skyung/categories/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">学习笔记</a>
              </p>
              <p class="item-title">
                <a href="/Skyung/2022/05/01/netty%E8%81%8A%E5%A4%A9%E5%AE%A4/" class="title">Netty聊天室</a>
              </p>
              <p class="item-date">
                <time datetime="2022-04-30T16:00:00.000Z" itemprop="datePublished">2022-05-01</time>
              </p>
            </div>
          </li>
          
      </ul>
    </div>
  </div>
  

    
  </div>
</aside>

  
  
  <aside class="sidebar sidebar-toc collapse   in  " id="collapseToc" itemscope itemtype="http://schema.org/WPSideBar">
  <div class="slimContent">
    <nav id="toc" class="article-toc">
      <h3 class="toc-title">文章目录</h3>
      <ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#string"><span class="toc-number">1.</span> <span class="toc-text">string</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#list"><span class="toc-number">2.</span> <span class="toc-text">list</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#hash"><span class="toc-number">3.</span> <span class="toc-text">hash</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#set"><span class="toc-number">4.</span> <span class="toc-text">set</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#zset"><span class="toc-number">5.</span> <span class="toc-text">zset</span></a></li></ol>
    </nav>
  </div>
</aside>

<main class="main" role="main">
  <div class="content">
  <article id="post-redis数据类型的数据结构和实现原理" class="article article-type-post" itemscope itemtype="http://schema.org/BlogPosting">
    
    <div class="article-header">
      
        
  
    <h1 class="article-title" itemprop="name">
      redis数据类型
    </h1>
  

      
      <div class="article-meta">
        <span class="article-date">
    <i class="icon icon-calendar-check"></i>
	<a href="/Skyung/2022/03/01/redis%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86/" class="article-date">
	  <time datetime="2022-02-28T16:00:00.000Z" itemprop="datePublished">2022-03-01</time>
	</a>
</span>
        
  <span class="article-category">
    <i class="icon icon-folder"></i>
    <a class="article-category-link" href="/Skyung/categories/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">学习笔记</a>
  </span>

        
  <span class="article-tag">
    <i class="icon icon-tags"></i>
	<a class="article-tag-link-link" href="/Skyung/tags/redis/" rel="tag">redis</a>
  </span>


        

        <span class="post-comment"><i class="icon icon-comment"></i> <a href="/Skyung/2022/03/01/redis%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86/#comments" class="article-comment-link">评论</a></span>
        
      </div>
    </div>
    <div class="article-entry marked-body" itemprop="articleBody">
      
        <h3 id="string"><a href="#string" class="headerlink" title="string"></a>string</h3><p>底层未简单动态字符串（simple dynamic string,SDS）相对于 C 语言对于字符串的定义，多出了 len 属性以及 free 属性。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">sdshdr</span>&#123;</span></span><br><span class="line">     <span class="comment">//记录buf数组中已使用字节的数量</span></span><br><span class="line">     <span class="comment">//等于 SDS 保存字符串的长度</span></span><br><span class="line">     <span class="type">int</span> len;</span><br><span class="line">     <span class="comment">//记录 buf 数组中未使用字节的数量</span></span><br><span class="line">     <span class="type">int</span> <span class="built_in">free</span>;</span><br><span class="line">     <span class="comment">//字节数组，用于保存字符串</span></span><br><span class="line">     <span class="type">char</span> buf[];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>用SDS保存字符串 “Redis”具体图示如下：</p>
<p><img src="https://gitee.com/lifuh/picgo/raw/master/img/image-20220301171312134.png" alt="image-20220301171312134"></p>
<p>len 保存了SDS保存字符串的长度</p>
<p>buf[] 数组用来保存字符串的每个元素</p>
<p>free 记录了 buf 数组中未使用的字节数量</p>
<p>这样实现有什么好处？</p>
<ul>
<li><p>由于 len 属性的存在，我们获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)，无需遍历数组。</p>
</li>
<li><p>进行两个字符串的拼接，会首先根据记录的 len 属性检查内存空间是否满足需求，如果不满足，会进行相应的空间扩展，不会出现缓冲区溢出。</p>
</li>
<li><p>减少修改字符串的内存重新分配次数：C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），由于len属性和free属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略。</p>
</li>
<li><p>二进制安全：C字符串以空字符作为字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括空字符串，因此C字符串无法正确存取； SDS 不是以空字符串来判断是否结束，而是以 len 属性表示的长度来判断字符串是否结束。</p>
</li>
</ul>
<h3 id="list"><a href="#list" class="headerlink" title="list"></a>list</h3><p>其底层有linkedList、zipList和quickList这三种存储方式。</p>
<p>linkedList是一个双向链表</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">typedf <span class="class"><span class="keyword">struct</span> <span class="title">listNode</span>&#123;</span></span><br><span class="line">    <span class="comment">//前一个节点</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">listNode</span> *<span class="title">prev</span>;</span></span><br><span class="line">    <span class="comment">//后一个节点</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">listNode</span> *<span class="title">next</span>;</span></span><br><span class="line">    <span class="comment">//当前节点的值的指针</span></span><br><span class="line">    <span class="type">void</span> *value;</span><br><span class="line">&#125;listNode;</span><br></pre></td></tr></table></figure>

<p>zipList数组</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">typedf <span class="class"><span class="keyword">struct</span> <span class="title">ziplist</span>&lt;</span>T&gt;&#123;</span><br><span class="line">    <span class="comment">//压缩列表占用字符数</span></span><br><span class="line">    int32 zlbytes;</span><br><span class="line">    <span class="comment">//最后一个元素距离起始位置的偏移量，用于快速定位最后一个节点</span></span><br><span class="line">    int32 zltail_offset;</span><br><span class="line">    <span class="comment">//元素个数</span></span><br><span class="line">    int16 zllength;</span><br><span class="line">    <span class="comment">//元素内容</span></span><br><span class="line">    T[] entries;</span><br><span class="line">    <span class="comment">//结束位 0xFF</span></span><br><span class="line">    int8 zlend;</span><br><span class="line">&#125;ziplist</span><br></pre></td></tr></table></figure>

<p>注意到zltail_offset这个参数，有了这个参数就可以快速定位到最后一个entry节点的位置，然后开始倒序遍历，也就是说zipList支持双向遍历。</p>
<p>quickList。qucikList是由zipList和双向链表linkedList组成的混合体。它将linkedList按段切分，每一段使用zipList来紧凑存储，多个zipList之间使用双向指针串接起来</p>
<p><img src="https://gitee.com/lifuh/picgo/raw/master/img/image-20220301171325991.png" alt="image-20220301171325991"></p>
<p>quickList内部默认单个zipList长度为8k字节，即list-max-ziplist-size的值设置为-2，超出了这个阈值，就会重新生成一个zipList来存储数据</p>
<h3 id="hash"><a href="#hash" class="headerlink" title="hash"></a>hash</h3><p>其底层实现方式有两种，一种是zipList，哈希对象保存的所有键值对的键和值的字符串长度都小于64字节哈希对象保存的键值对数量小于512个使用zipList；另一种是字典dict</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">typedf <span class="class"><span class="keyword">struct</span> <span class="title">dict</span>&#123;</span></span><br><span class="line">    dictType *type;<span class="comment">//类型特定函数，包括一些自定义函数，这些函数使得key和value能够存储</span></span><br><span class="line">    <span class="type">void</span> *private;<span class="comment">//私有数据</span></span><br><span class="line">    dictht ht[<span class="number">2</span>];<span class="comment">//两张hash表 </span></span><br><span class="line">    <span class="type">int</span> rehashidx;<span class="comment">//rehash索引，字典没有进行rehash时，此值为-1</span></span><br><span class="line">    <span class="type">unsigned</span> <span class="type">long</span> iterators; <span class="comment">//正在迭代的迭代器数量</span></span><br><span class="line">&#125;dict;</span><br></pre></td></tr></table></figure>

<p>由上面可以看出，dict本质上是对哈希表dictht的一个简单封装，dictht的定义如下所示</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">typedf <span class="class"><span class="keyword">struct</span> <span class="title">dictht</span>&#123;</span></span><br><span class="line">    dictEntry **table;<span class="comment">//存储数据的数组 二维</span></span><br><span class="line">    <span class="type">unsigned</span> <span class="type">long</span> size;<span class="comment">//数组的大小</span></span><br><span class="line">    <span class="type">unsigned</span> <span class="type">long</span> sizemask;<span class="comment">//哈希表的大小的掩码，用于计算索引值，总是等于 size-1</span></span><br><span class="line">    <span class="type">unsigned</span> <span class="type">long</span> used;<span class="comment">//// 哈希表中中元素个数</span></span><br><span class="line">&#125;dictht;</span><br></pre></td></tr></table></figure>

<p>真正存储数据的结构是dictEntry数组，其结构定义如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">typedf <span class="class"><span class="keyword">struct</span> <span class="title">dictEntry</span>&#123;</span></span><br><span class="line">    <span class="type">void</span> *key;<span class="comment">//键</span></span><br><span class="line">    <span class="class"><span class="keyword">union</span>&#123;</span></span><br><span class="line">        <span class="type">void</span> val;</span><br><span class="line">        <span class="type">unit64_t</span> u64;</span><br><span class="line">        <span class="type">int64_t</span> s64;</span><br><span class="line">        <span class="type">double</span> d;</span><br><span class="line">    &#125;v;<span class="comment">//值</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">dictEntry</span> *<span class="title">next</span>；//指向下一个节点的指针</span></span><br><span class="line"><span class="class">&#125;<span class="title">dictEntry</span>;</span></span><br></pre></td></tr></table></figure>

<p>标准hashtable，用数组储存key，链表处理冲突</p>
<h3 id="set"><a href="#set" class="headerlink" title="set"></a>set</h3><p>其底层有两种实现方式，当value是整数值时，且数据量不大时使用inset来存储，其他情况都是用字典dict来存储。</p>
<p>Redis中inset的结构定义如下所示</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">typedf <span class="class"><span class="keyword">struct</span> <span class="title">inset</span>&#123;</span></span><br><span class="line">    <span class="type">uint32_t</span> encoding;<span class="comment">//编码方式 有三种 默认 INSET_ENC_INT16</span></span><br><span class="line">    <span class="type">uint32_t</span> length;<span class="comment">//集合元素个数</span></span><br><span class="line">    <span class="type">int8_t</span> contents[];<span class="comment">//实际存储元素的数组 从小到大排列</span></span><br><span class="line">&#125;inset;</span><br><span class="line"><span class="meta">#<span class="keyword">define</span> INTSET_ENC_INT16 (sizeof(int16_t))   <span class="comment">//16位，2个字节，表示范围-32,768~32,767</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> INTSET_ENC_INT32 (sizeof(int32_t))   <span class="comment">//32位，4个字节，表示范围-2,147,483,648~2,147,483,647</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> INTSET_ENC_INT64 (sizeof(int64_t))   <span class="comment">//64位，8个字节，表示范围-9,223,372,036,854,775,808~9,223,372,036,854,775,807</span></span></span><br></pre></td></tr></table></figure>

<h3 id="zset"><a href="#zset" class="headerlink" title="zset"></a>zset</h3><p>zset也有两种不同的实现，分别是zipList和skipList；当[score,value]键值对数量少于128个；每个元素的长度小于64字节时采用zipList</p>
<p>ziplist编码的有序集合对象底层实现是压缩列表，其结构是两个紧密相连的压缩列表节点，第一个保存元素的成员，第二个保存元素的分值，而且分值小的靠近表头，大的靠近表尾。</p>
<p>skipList跳表可以保证增、删、查等操作时的时间复杂度为O(logN)，这个性能可以与平衡树相媲美，但实现方式上却更加简单，唯一美中不足的就是跳表占用的空间比较大，其实就是一种空间换时间的思想</p>
<p><img src="https://gitee.com/lifuh/picgo/raw/master/img/image-20220301171343457.png" alt="image-20220301171343457"></p>
<p>Redis中跳表一个节点最高可以达到64层，一个跳表中最多可以存储2^64个元素。跳表中，每个节点都是一个skiplistNode</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">typedf <span class="class"><span class="keyword">struct</span> <span class="title">zskiplist</span>&#123;</span></span><br><span class="line">    <span class="comment">//头节点</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">zskiplistNode</span> *<span class="title">header</span>;</span></span><br><span class="line">    <span class="comment">//尾节点</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">zskiplistNode</span> *<span class="title">tail</span>;</span></span><br><span class="line">    <span class="comment">// 跳表中元素个数</span></span><br><span class="line">    <span class="type">unsigned</span> <span class="type">long</span> length;</span><br><span class="line">    <span class="comment">//目前表内节点的最大层数</span></span><br><span class="line">    <span class="type">int</span> level;</span><br><span class="line">&#125;zskiplist;</span><br><span class="line"></span><br><span class="line">typedf <span class="class"><span class="keyword">struct</span> <span class="title">zskiplistNode</span>&#123;</span></span><br><span class="line">    sds ele;<span class="comment">// 具体的数据</span></span><br><span class="line">    <span class="type">double</span> score;<span class="comment">// 分数</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">zskiplistNode</span> *<span class="title">backward</span>;</span><span class="comment">//后退指针</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">zskiplistLevel</span>&#123;</span>  </span><br><span class="line">        <span class="class"><span class="keyword">struct</span> <span class="title">zskiplistNode</span> *<span class="title">forward</span>;</span><span class="comment">//前进指针forward</span></span><br><span class="line">        <span class="type">unsigned</span> <span class="type">int</span> span;<span class="comment">//跨度span</span></span><br><span class="line">    &#125;level[];<span class="comment">//层级数组 最大32</span></span><br><span class="line">&#125;zskiplistNode;</span><br></pre></td></tr></table></figure>

<p><img src="https://gitee.com/lifuh/picgo/raw/master/img/image-20220301171410132.png" alt="image-20220301171410132"></p>
<p>参考<a target="_blank" rel="noopener" href="https://www.cnblogs.com/reecelin/p/13368374.html">Redis底层数据结构之 zset - 凡尘多遗梦 - 博客园 (cnblogs.com)</a></p>

      
    </div>
    <div class="article-footer">
      <blockquote class="mt-2x">
  <ul class="post-copyright list-unstyled">
    
    <li class="post-copyright-link hidden-xs">
      <strong>本文链接：</strong>
      <a href="https://skyung.gitee.io/Skyung/2022/03/01/redis%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86/" title="redis数据类型" target="_blank" rel="external">https://skyung.gitee.io/Skyung/2022/03/01/redis数据类型的数据结构和实现原理/</a>
    </li>
    
    <li class="post-copyright-license">
      <strong>版权声明： </strong> 本博客所有文章除特别声明外，均采用 <a href="http://creativecommons.org/licenses/by/4.0/deed.zh" target="_blank" rel="external">CC BY 4.0 CN协议</a> 许可协议。转载请注明出处！
    </li>
  </ul>
</blockquote>


<div class="panel panel-default panel-badger">
  <div class="panel-body">
    <figure class="media">
      <div class="media-left">
        <a href="https://github.com/cofess" target="_blank" class="img-burn thumb-sm visible-lg">
          <img src="/Skyung/images/avatar.jpg" class="img-rounded w-full" alt="">
        </a>
      </div>
      <div class="media-body">
        <h3 class="media-heading"><a href="https://github.com/cofess" target="_blank"><span class="text-dark">Skyung</span><small class="ml-1x">Web Developer</small></a></h3>
        <div>脚踏实地，仰望星空</div>
      </div>
    </figure>
  </div>
</div>


    </div>
  </article>
  
    
  <section id="comments">
  	
      <div id="uyan_frame"></div>
    
  </section>


  
</div>

  <nav class="bar bar-footer clearfix" data-stick-bottom>
  <div class="bar-inner">
  
  <ul class="pager pull-left">
    
    <li class="prev">
      <a href="/Skyung/2022/03/01/java%E7%BA%BF%E7%A8%8B%E6%B1%A0/" title="java线程池"><i class="icon icon-angle-left" aria-hidden="true"></i><span>&nbsp;&nbsp;上一篇</span></a>
    </li>
    
    
    <li class="next">
      <a href="/Skyung/2022/03/01/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F%E2%80%94%E5%88%9B%E5%BB%BA%E5%9E%8B%E6%A8%A1%E5%BC%8F/" title="设计模式—创建型模式"><span>下一篇&nbsp;&nbsp;</span><i class="icon icon-angle-right" aria-hidden="true"></i></a>
    </li>
    
    
    <li class="toggle-toc">
      <a class="toggle-btn " data-toggle="collapse" href="#collapseToc" aria-expanded="false" title="文章目录" role="button">    <span>[&nbsp;</span><span>文章目录</span>
        <i class="text-collapsed icon icon-anchor"></i>
        <i class="text-in icon icon-close"></i>
        <span>]</span>
      </a>
    </li>
    
  </ul>
  
  
  <!-- Button trigger modal -->
  <button type="button" class="btn btn-fancy btn-donate pop-onhover bg-gradient-warning" data-toggle="modal" data-target="#donateModal"><span>赏</span></button>
  <!-- <div class="wave-icon wave-icon-danger btn-donate" data-toggle="modal" data-target="#donateModal">
    <div class="wave-circle"><span class="icon"><i class="icon icon-bill"></i></span></div>
  </div> -->
  
  
  <div class="bar-right">
    
    <div class="share-component" data-sites="weibo,qq,wechat,facebook,twitter" data-mobile-sites="weibo,qq,qzone"></div>
    
  </div>
  </div>
</nav>
  
<!-- Modal -->
<div class="modal modal-center modal-small modal-xs-full fade" id="donateModal" tabindex="-1" role="dialog">
  <div class="modal-dialog" role="document">
    <div class="modal-content donate">
      <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">&times;</span></button>
      <div class="modal-body">
        <div class="donate-box">
          <div class="donate-head">
            <p>感谢您的支持，我会继续努力的!</p>
          </div>
          <div class="tab-content">
            <div role="tabpanel" class="tab-pane fade active in" id="alipay">
              <div class="donate-payimg">
                <img src="/Skyung/images/donate/alipay.jpg" alt="扫码支持" title="扫一扫" />
              </div>
              <p class="text-muted mv">扫码打赏，你说多少就多少</p>
              <p class="text-grey">打开支付宝扫一扫，即可进行扫码打赏哦</p>
            </div>
            <div role="tabpanel" class="tab-pane fade" id="wechatpay">
              <div class="donate-payimg">
                <img src="/Skyung/images/donate/wechat.jpg" alt="扫码支持" title="扫一扫" />
              </div>
              <p class="text-muted mv">扫码打赏，你说多少就多少</p>
              <p class="text-grey">打开微信扫一扫，即可进行扫码打赏哦</p>
            </div>
          </div>
          <div class="donate-footer">
            <ul class="nav nav-tabs nav-justified" role="tablist">
              <li role="presentation" class="active">
                <a href="#alipay" id="alipay-tab" role="tab" data-toggle="tab" aria-controls="alipay" aria-expanded="true"><i class="icon icon-alipay"></i> 支付宝</a>
              </li>
              <li role="presentation" class="">
                <a href="#wechatpay" role="tab" id="wechatpay-tab" data-toggle="tab" aria-controls="wechatpay" aria-expanded="false"><i class="icon icon-wepay"></i> 微信支付</a>
              </li>
            </ul>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>



</main>

  <footer class="footer" itemscope itemtype="http://schema.org/WPFooter">
	
	
    <ul class="social-links">
    	
        <li><a href="/Skyung/null" target="_blank" title="Github" data-toggle=tooltip data-placement=top><i class="icon icon-github"></i></a></li>
        
        <li><a href="/Skyung/null" target="_blank" title="Weibo" data-toggle=tooltip data-placement=top><i class="icon icon-weibo"></i></a></li>
        
        <li><a href="/Skyung/null" target="_blank" title="Twitter" data-toggle=tooltip data-placement=top><i class="icon icon-twitter"></i></a></li>
        
        <li><a href="/Skyung/null" target="_blank" title="Behance" data-toggle=tooltip data-placement=top><i class="icon icon-behance"></i></a></li>
        
        <li><a href="/Skyung/atom.xml" target="_blank" title="Rss" data-toggle=tooltip data-placement=top><i class="icon icon-rss"></i></a></li>
        
    </ul>

    <div class="copyright">
    	
        <div class="publishby">
        	Theme by <a href="https://github.com/cofess" target="_blank"> cofess </a>base on <a href="https://github.com/cofess/hexo-theme-pure" target="_blank">pure</a>.
        </div>
    </div>
</footer>
  <script src="//cdn.jsdelivr.net/npm/jquery@1.12.4/dist/jquery.min.js"></script>
<script>
window.jQuery || document.write('<script src="js/jquery.min.js"><\/script>')
</script>

<script src="/Skyung/js/plugin.min.js"></script>


<script src="/Skyung/js/application.js"></script>


    <script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: '文章',
            PAGES: '页面',
            CATEGORIES: '分类',
            TAGS: '标签',
            UNTITLED: '(未命名)',
        },
        ROOT_URL: '/Skyung/',
        CONTENT_URL: '/Skyung/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>

<script src="/Skyung/js/insight.js"></script>






   




   
    
    <script defer type="text/javascript" src="http://v2.uyan.cc/code/uyan.js?uid=[object Object]"></script>








</body>
</html>